class Solution {
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        constexpr int MOD = 1'000'000'007;
        int m = grid.size(), n = grid[0].size();
        vector f(n + 1, vector<int>(k));
        f[1][0] = 1;
        vector<int> new_f(k); // 避免在循环内反复创建 vector
        for (auto& row : grid) {
            for (int j = 0; j < n; j++) {
                for (int s = 0; s < k; s++) {
                    int new_s = (s + row[j]) % k;
                    new_f[s] = (f[j + 1][new_s] + f[j][new_s]) % MOD;
                }
                ranges::copy(new_f, f[j + 1].begin()); // 把 new_f 复制到 f[j+1] 中
            }
        }
        return f[n][0];
    }
};